<?php

//
interface Algorithm
{
    public function Sort(Array $arr);
}

trait find
{
    function halfFind($x, $arr)
    {
        $length = count($arr);
        if ($length <= 0) {
            return -1;
        }
        $minKey = 0;
        $maxKey = $length - 1;
        while ($minKey <= $maxKey) {
            $middleKey = floor(($minKey + $maxKey) / 2);
            if ($x > $arr[$middleKey]) {
                $minKey = $middleKey + 1;
            } elseif ($x < $arr[$middleKey]) {
                $maxKey = $middleKey - 1;
            } else {
                return $middleKey;
            }
        }
        return -1;
    }
}


class MaoPaoSort implements Algorithm
{
    function Sort(Array $arr)
    {
        // TODO: Implement Sort() method.
        $length = count($arr);
        if ($length <= 0) {
            return false;
        }
        for ($i = 0; $i < $length - 1; $i++) {
            for ($j = 0; $j < $length - $i - 1; $j++) {
                if ($arr[$j] > $arr[$j + 1]) {
                    $tem = $arr[$j];
                    $arr[$j] = $arr[$j + 1];
                    $arr[$j + 1] = $tem;
                }
            }
        }
        return $arr;
    }
}

class InsertSort implements Algorithm
{
    public function Sort(Array $arr)
    {
        // TODO: Implement Sort() method.
        $length = count($arr);
        if ($length <= 0) {
            return false;
        }
        for ($i = 0; $i < $length; $i++) {
            $key = $i - 1;
            $value = $arr[$i];
            while ($key >= 0 && $arr[$key] < $value) {
                $arr[$key + 1] = $arr[$key];
                $key--;
            }
            $arr[$key + 1] = $value;
        }
        return $arr;
    }
}

class ChangeSort implements Algorithm
{
    public function Sort(array $arr)
    {
        // TODO: Implement Sort() method.
        $length = count($arr);
        if ($length <= 0) {
            return false;
        }
        for ($i = 0; $i < $length - 1; $i++) {
            $maxKey = $i;
            for ($j = $i; $j < $length; $j++) {
                if ($arr[$j] > $arr[$maxKey]) {
                    $maxKey = $j;
                }
            }
            if ($maxKey != $i) {
                $tem = $arr[$maxKey];
                $arr[$maxKey] = $arr[$i];
                $arr[$i] = $tem;
            }
        }
        return $arr;
    }
}

class QuickSort implements Algorithm
{
    public function Sort(array $arr)
    {
        // TODO: Implement Sort() method.
        $length = count($arr);
        if ($length <= 1) {
            return $arr;
        }
        $left = $right = [];
        for ($i = 1; $i < $length; $i++) {
            if ($arr[$i] < $arr[0]) {
                $right[] = $arr[$i];
            } else {
                $left[] = $arr[$i];
            }
        }
        $leftArr = $this->Sort($left);
        $rightArr = $this->Sort($right);
        return array_merge($leftArr, [$arr[0]], $rightArr);
    }
}

class FindArr
{
    use find;
}

abstract class test
{
    public static $test = 1;
    public $test3 = 3;
    abstract function bus();
    public static function fun1(){
        echo "fun1" . PHP_EOL;
    }
}

class test1 extends test
{
    public function bus()
    {
        // TODO: Implement bus() method.
        echo "bus" . PHP_EOL;
    }
}

$a = new test1();
$a->bus();
$a::fun1();

$arr = [1, 10, 6, 5, 7, 3, 4, 9, 8, 2, 11];
$maoPaoSort = new MaoPaoSort();
$maoPaoSortArr = $maoPaoSort->Sort($arr);

$insertSort = new InsertSort();
$insertSortArr = $insertSort->Sort($arr);

$changeSort = new ChangeSort();
$changeSortArr = $changeSort->Sort($arr);

$quickSort = new QuickSort();
$quickSortArr = $quickSort->Sort($arr);

$half = new FindArr();
var_dump($half);